Increasingly, programs are written to execute using arrays of standard processors in parallel. Software supervisor systems are then written to enable an application programmer to harness these processors and orchestrate the efficient cooperation of each processing unit in achieving overall programming goals. Such a software supervisor is referred to in the art as a parallel "microkernel". Taken as a collective, these microkernels create an application program environment similar to that created by any monolithic kernel or operating system.
Parallel microkernels are similar to monolithic kernels in that they manage the resources of the machine environment around them. There is, however, a significant difference between parallel and monolithic kernels. In particular, monolithic kernels seek to fairly divide a machine environment among competitive task contexts over time. A parallel microkernel, on the other hand, is generally written to efficiently direct the capabilities of each machine environment in achieving a single goal, i.e., the efficient completion of the individual kernel's portion of the parallel application. Within a parallel microkernel, the component tasks are never really competitive since they are working within one application program toward a single goal.
Central to any kernel's duties is the scheduling and descheduling of control contexts. Control contexts are given different names such as "threads," "processes," or "tasks" depending upon the properties of the context and the naming conventions of the kernel. A context is left in control of a machine environment until it either yields, is blocked waiting for something, or is interrupted. These are called descheduling events since it is at that time that scheduling algorithms are evaluated for priority of context execution. In nonpreemptive scheduling, user contexts are never switched as a result of an interrupt. All processor interrupts eventually return to the context processing at the time of the interruption.
In a nonpreemptive parallel microkernel, an application programmer controls context scheduling. This is done either indirectly, by programming in a single threaded model, or directly, by yielding between multiple context. In the former case, there is only a single application context per machine environment and thus from the programmer's perspective, it should always be scheduled when ready to run. In the later case, the programmer will specifically yield or make a blocking kernel call to control the scheduling of participating user contexts. In both cases, a call to a microkernel service may block the running context and cause an evaluation of the scheduling algorithm(s). In either case, a context switch is often redundant. This is because the microkernel, after evaluating the scheduling algorithm(s) often determines that the priority context is exactly the context that has yielded or blocked.
Therein lies the problem. In standard kernel context scheduling, a complete context switch is performed whenever there is occasion to reevaluate the scheduling algorithm. The assumption is that there is a high likelihood that the next context given priority will be other than the context which has yielded or blocked. In a parallel microkernel environment this is a bad assumption. In fact, there is a high probability that there will be a redundant context switch as a context finds itself continuously rescheduled to execute. Thus, a need exists in the data processing art for a scheduling method which does not incur the heavy overhead of a context switch when evaluation of the scheduling algorithm will probably show it to be redundant.